package org.hot100_3;

public class leetcode560 {

    public int subarraySum3(int[] nums, int k) {

        int n = nums.length;
        int[] preSum = new int[n + 1];
        int count = 0;
        //前缀和，不包括当前元素
        preSum[0] = 0;
        for (int i = 1; i <= n; i++) {
            preSum[i] = preSum[i - 1] + nums[i - 1];
        }
        //需要考虑当前元素是否等于k，如left指向的元素为3，k=3。
        //在right==left时，preSum[right + 1] - preSum[left]就是left指向的元素
        for (int left = 0; left < n; left++) {
            for (int right = left; right < n; right++) {
                int sum = preSum[right + 1] - preSum[left];
                if (sum == k) {
                    count++;
                }
            }
        }
        return count;
    }


    //前缀和
    public int subarraySum2(int[] nums, int k) {

        int count = 0;

        int n = nums.length;

        int[] preSum = new int[n];

        preSum[0] = nums[0];

        for (int i = 1; i < n; i++) {
            preSum[i] = preSum[i - 1] + nums[i];
        }

        for (int left = 0; left < n; left++) {
            for (int right = left; right < n; right++) {
                int sum = 0;
                if (left == right) {
                    if (left == 0) {
                        sum = preSum[left];
                    } else {
                        sum = preSum[right] - preSum[left - 1];
                    }
                } else {
                    sum = preSum[right] - preSum[left];
                }

                if (sum == k) {
                    count++;
                }
            }
        }

        return count;
    }


    //超时
    public int subarraySum(int[] nums, int k) {

        for (int i = 0; i < nums.length; i++) {
            backtracking(nums, i, 0, k);
        }

        return count;
    }

    int count = 0;

    private void backtracking(int[] nums, int index, int sum, int k) {

        if (index == nums.length) {
            return;
        }

        sum += nums[index];

        if (sum == k) {
            count++;
        }

        backtracking(nums, index + 1, sum, k);

    }
}
